package com.dy.分类.哈希表和字符串._76_最小覆盖子串;

import java.util.HashMap;

/*
给定一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字母的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

 */
public class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> map = new HashMap<>();
        //统计目标串中的字符及其个数
        for (Character c : t.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0, minLen = Integer.MAX_VALUE, index = 0, matchCount = 0;
        for (; right < s.length(); right++) {
            Character rightCharacter = s.charAt(right);
            Integer count = map.get(rightCharacter);
            if (count == null) {
                continue;
            }
            //如果匹配到了，将map中的count-1
            count--;
            map.put(rightCharacter, count);
            //如果该字符都匹配完了，则让matchCount+1
            if (count == 0) {
                matchCount++;
            }
            //当目前窗口包含所有的目标字符时，更新最小长度,并用index记录left的位置
            for (;matchCount == map.size();left++) {
                if (minLen > right-left + 1) {
                    minLen = right-left + 1;
                    index = left;
                }

                Character leftCharacter = s.charAt(left);
                count = map.get(leftCharacter);
                if (count == null) {
                    continue;
                }

                //如果left所在字符是目标，则让map+1
                count++;
                map.put(leftCharacter, count);
                //如果匹配的字符串为1，则说明matchCount需要-1
                if (count == 1) {
                    matchCount--;
                }


            }
        }
        //当minLen还是那么长时，说明没有匹配到，返回空，否则返回子字符串
        return minLen==Integer.MAX_VALUE?"":s.substring(index,index+minLen);
    }

}
